package com.fjl.list.leetcode206;

import com.fjl.list.ListNode;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/2/21 14:54
 */
public class ReverseNListClass {
    // 将链表的前 n 个节点反转（n <= 链表长度）
    ListNode reverseN(ListNode head, int n) {
        // 空链表或者单个节点的链表直接原样return
        if (head == null || head.next == null) return head;

        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (n > 0) {
            cur.next = pre;
            n--;
            // 更新指针位置
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
        }
        head.next = cur;
        return pre;
    }


    // 后驱节点
    ListNode successor = null;
    ListNode reverseN1(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        ListNode last = reverseN1(head.next, n-1);
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }
    /*
    1、base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点，即要记录第 n + 1 个节点。

    2、刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。
     */
}
